from random import choice
from time import time

class OthelloBoard:

    def __init__(self):
        self.board = ([' '] * 8, [' '] * 8, [' '] * 8, [' '] * 8 , [' '] * 8 , [' '] * 8 , [' '] * 8 , [' '] * 8)
        self.size = 8
        self.board[4][4] = 'W'
        self.board[3][4] = 'B'
        self.board[3][3] = 'W'
        self.board[4][3] = 'B'
        # a list of unit vectors (row, col)
        self.directions = [ (-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        

    def print_board(self):
        '''
        Prints the board
        '''
        print("  0 1 2 3 4 5 6 7")
        linestr = " "
        for j in range(self.size):
            linestr = linestr + "+-"
        linestr = linestr + "+"
        for i in range(self.size):
            strng = str(i) + "|"
            print(linestr)
            for k in range(self.size):
                strng = strng + self.board[i][k] + "|"
            print(strng)
        print(linestr)

    def copy_board(self, board):
        '''
        Copies the entire board
        '''
        for i in range(self.size):
            for j in range(self.size):
                self.board[i][j] = board.board[i][j]

    def count_blanks(self):
        '''
        Counts all unassigned squares
        '''
        blanks = 0
        for i in range(self.size):
            for j in range(self.size):
                if self.get_square(i, j) == " ":
                    blanks += 1
        return blanks
                    
    def full_board(self):
        '''
        Returns true if no square in the board contains "_", false otherwise
        '''
        for i in range(self.size):
            for j in range(self.size):
                if self.get_square(i, j) == " ":
                    return False
        return True

    def score(self, player, opp):
        '''
        Determines the score of the board by adding +1 for every tile owned by player, 
        and -1 for every tile owned by opp
        '''
        score = 0
        for i in range(self.size):
            for j in range(self.size):
                if(self.get_square(i, j) == player):
                    score += 1
                elif(self.get_square(i, j) == opp):
                    score -= 1
        return score

    def print_score(self):
        sc = self.score('B', 'W')
        print("B: " + str(sc) + " | W: " + str(-sc))

    def play_square(self, col, row, player, opp):
        '''
        Returns true if the square was played, false if the move is not allowed
        '''
        if(self.get_square(col, row) != " "):
            return False
        if(player == opp):
            print("player and opponent cannot be the same")
            return False
        legal = False
        #for each direction, check to see if the move is legal by seeing if the adjacent square
        #in that direction is occupied by the opponent. If it isnt check the next direction.
        #if it is, check to see if one of the players pieces is on the board beyond the oppponents piece,
        #if the chain of opponents pieces is flanked on both ends by the players pieces, flip
        #the opponents pieces 
        for Dir in self.directions:
            #look across the length of the board to see if the neighboring squares are empty,
            #held by the player, or held by the opponent
            for i in range(self.size):
                if  (((row + i * Dir[0]) < self.size)  and ((row + i * Dir[0]) >= 0) and ((col + i * Dir[1]) >= 0) and ((col + i * Dir[1]) < self.size)):
                    #does the adjacent square in direction dir belong to the opponent?
                    if self.get_square(col + i * Dir[1], row + i * Dir[0]) != opp and i == 1 : # no
                        #no pieces will be flipped in this direction, so skip it
                        break
                    #yes the adjacent piece belonged to the opponent, now lets see if there are a chain
                    #of opponent pieces
                    if self.get_square(col + i * Dir[1], row + i * Dir[0]) == " " and i != 0 :
                        break

                    #with one of player's pieces at the other end
                    if self.get_square(col + i * Dir[1], row + i * Dir[0]) == player and i != 0 and i != 1 :
                        #set a flag so we know that the move was legal
                        legal = True
                        self.flip_tiles(row, col, Dir, i, player)
                        break
        return legal

    def flip_tiles(self, row, col, Dir, dist, player):
        '''
        Sets all tiles along a given direction (Dir) from a given starting point (col and row) 
        for a given distance (dist) to be a given value (player)
        '''
        for i in range(dist):
            self.board[row + i * Dir[0]][col + i * Dir[1]] = player
        return True
    
    def get_square(self, col, row):
        '''
        Returns the value of a square on the board
        '''
        return self.board[row][col]

    def has_move(self, player, opp):
        '''
        Checks all board positions to see if there is a legal move
        '''
        for i in range(self.size):
            for j in range(self.size):
                if self.islegal(i, j, player, opp):
                    return True
        return False

    def islegal(self, col, row, player, opp):
        '''
        Checks every direction from the position which is input via "col" and "row", 
        to see if there is an opponent piece in one of the directions. If the input 
        position is adjacent to an opponents piece, this function looks to see if there 
        is a chain of opponent pieces in that direction, which ends with one of the players pieces. 
        '''
        if(self.get_square(col, row) != " "):
            return False
        for Dir in self.directions:
            for i in range(self.size):
                if  (((row + i * Dir[0]) < self.size)  and ((row + i * Dir[0]) >= 0) and ((col + i * Dir[1]) >= 0) and ((col + i * Dir[1]) < self.size)):
                    #does the adjacent square in direction dir belong to the opponent?
                    if self.get_square(col + i * Dir[1], row + i * Dir[0]) != opp and i == 1 : # no
                        #no pieces will be flipped in this direction, so skip it
                        break
                    #yes the adjacent piece belonged to the opponent, now lets see if there are a chain
                    #of opponent pieces
                    if self.get_square(col + i * Dir[1], row + i * Dir[0]) == " " and i != 0 :
                        break

                    #with one of player's pieces at the other end
                    if self.get_square(col + i * Dir[1], row + i * Dir[0]) == player and i != 0 and i != 1 :
                        #set a flag so we know that the move was legal
                        return True
        return False
    
    def is_ended(self):
        '''
        Check if the game has ended
        '''
        if self.full_board() == True:
            return True
        elif ((not self.has_move('B', 'W')) and (not self.has_move('W', 'B'))):
            return True
        else:
            return False     

def make_simple_cpu_move(board, cpuval, oppval):
    '''
    The cpu will search the game board for a legal move, and play the first one it finds
    '''
    for i in range(board.size):
        for j in range(board.size):
            if(board.islegal(i, j, cpuval, oppval)):
                board.play_square(i, j, cpuval, oppval)
                print("CPU has played row: " + str(j) + "  col: " + str(i))
                return True
    return False


def make_minimax_cpu_move(board, cpuval, oppval):
    '''
    Minimax algorithm which contains the alpha-beta pruning
    '''
    actions = {}
    max_depth = board.count_blanks()
    start_time = time()

    for limit in range(max_depth):
        now_time = time()
        if now_time - start_time > 20:
            continue
        for i in range(board.size):
            now_time = time()
            if now_time - start_time > 20:
                continue
            for j in range(board.size):
                now_time = time()
                if now_time - start_time > 20:
                    continue
                if(board.islegal(i, j, cpuval, oppval)):
                    now_time = time()
                    if now_time - start_time > 20:
                        continue
                    new_board = OthelloBoard()
                    new_board.copy_board(board)
                    new_board.play_square(i, j, cpuval, oppval)
                    test = min_value(new_board, cpuval, oppval, -1000000, 1000000, limit, start_time, i, j)
                    if test not in actions:
                        actions[test] = []
                    if [i, j] not in actions[test]:
                        actions[test].append([i, j])
                    
    print('Search took',now_time - start_time,'seconds')
    
    util_list = sorted(actions.keys(), reverse=True)
    i, j = choice(actions[util_list[0]])
    print('Utility of choice:', util_list[0])
        
    if(board.islegal(i, j, cpuval, oppval)):
        board.play_square(i, j, cpuval, oppval)
        print("CPU has played row: " + str(j) + "  col: " + str(i))
        return True
    return False

def min_value(board, cpuval, oppval, alpha, beta, limit, start_time, new_c, new_r):
    now_time = time()
    if now_time - start_time > 20 or limit == 0 or board.is_ended() or board.has_move(oppval, cpuval):
        return evaluate(board, cpuval, oppval, new_c, new_r)
    else:
        val = 1000000
        for i in range(board.size):
            for j in range(board.size):
                if(board.islegal(i, j, cpuval, oppval)):
                    new_board = OthelloBoard()
                    new_board.copy_board(board)
                    new_board.play_square(i, j, oppval, cpuval)

                    val = min(val, max_value(new_board, cpuval, oppval, alpha, beta, limit - 1, start_time, i, j))
                    if(val <= alpha):
                        return val
                    beta = min(beta, val)
        return val

def max_value(board, cpuval, oppval, alpha, beta, limit, start_time, new_c, new_r):
    now_time = time()
    if now_time - start_time > 20 or limit == 0 or board.is_ended() or board.has_move(cpuval, oppval):
        return evaluate(board, cpuval, oppval, new_c, new_r)
    else:
        val = -1000000
        for i in range(board.size):
            for j in range(board.size):
                if(board.islegal(i, j, cpuval, oppval)):
                    new_board = OthelloBoard()
                    new_board.copy_board(board)
                    new_board.play_square(i, j, cpuval, oppval)

                    val = max(val, min_value(new_board, cpuval, oppval, alpha, beta, limit - 1, start_time, i, j))
                    if(val >= beta):
                        return val
                    alpha = max(alpha, val)
        return val

def evaluate(board, cpuval, oppval, new_c, new_r):
    util = 0
    for row in list(range(8)):
        for col in list(range(8)):
            # if the square is taken
            if board.board[row][col] != ' ':
                # if the current square is taken in the new move
                if row == new_r and col == new_c:
                    # assign large values to corners and sides
                    if ((row == 0 and col == 0) or (row == 0 and col == 7) 
                        or (row == 7 and col == 0) or (row == 7 and col == 7)):
                        if board.board[row][col] == cpuval:
                            util += 30
                        elif board.board[row][col] == oppval:
                            util -= 30
                    elif (((row == 0  or row == 7) and col != 0 and col != 7) 
                        or ((col == 0 or col == 7) and row != 0 and row != 7)):
                        if board.board[row][col] == cpuval:
                            util += 10
                        elif board.board[row][col] == oppval:
                            util -= 10
                    # assign normal values to occupied squares
                    else:
                        if board.board[row][col] == cpuval:
                            util += 1
                        elif board.board[row][col] == oppval:
                            util -= 1

                # if the current square is not taken in the new move
                else:
                    if board.board[row][col] == cpuval:
                        util += 1
                    elif board.board[row][col] == oppval:
                        util -= 1

            # accounting for the mobility of players
            elif board.islegal(col, row, cpuval, oppval):
                    util += 1
            elif board.islegal(col, row, oppval, cpuval):
                    util -= 1
            
    # account for C-squares                                
    if ((new_r == 1 and new_c == 0) or (new_r == 0 and new_c == 1)):
        if board.board[new_r][new_c] == cpuval and board.board[new_r][new_c] != board.board[0][0]:
            util -= 5
        elif board.board[new_r][new_c] == oppval and board.board[new_r][new_c] != board.board[0][0]:
            util += 5
    if ((new_r == 1 and new_c == 7) or (new_r == 0 and new_c == 6)):
        if board.board[new_r][new_c] == cpuval and board.board[new_r][new_c] != board.board[0][0]:
            util -= 5
        elif board.board[new_r][new_c] == oppval and board.board[new_r][new_c] != board.board[0][0]:
            util += 5
    if ((new_r == 6 and new_c == 0) or (new_r == 7 and new_c == 1)):
        if board.board[new_r][new_c] == cpuval and board.board[new_r][new_c] != board.board[0][0]:
            util -= 5
        elif board.board[new_r][new_c] == oppval and board.board[new_r][new_c] != board.board[0][0]:
            util += 5
    if ((new_r == 6 and new_c == 7) or (new_r == 7 and new_c == 6)):
        if board.board[new_r][new_c] == cpuval and board.board[new_r][new_c] != board.board[0][0]:
            util -= 5
        elif board.board[new_r][new_c] == oppval and board.board[new_r][new_c] != board.board[0][0]:
            util += 5
            
    # account for X-squares
    if (new_r == 1 and new_c == 1):
        if board.board[new_r][new_c] == cpuval and board.board[new_r][new_c] != board.board[0][0]:
            util -= 10
        elif board.board[new_r][new_c] == oppval and board.board[new_r][new_c] != board.board[0][0]:
            util += 10
    if (new_r == 1 and new_c == 6):
        if board.board[new_r][new_c] == cpuval and board.board[new_r][new_c] != board.board[0][0]:
            util -= 10
        elif board.board[new_r][new_c] == oppval and board.board[new_r][new_c] != board.board[0][0]:
            util += 10
    if (new_r == 6 and new_c == 1):
        if board.board[new_r][new_c] == cpuval and board.board[new_r][new_c] != board.board[0][0]:
            util -= 10
        elif board.board[new_r][new_c] == oppval and board.board[new_r][new_c] != board.board[0][0]:
            util += 10
    if (new_r == 6 and new_c == 6):
        if board.board[new_r][new_c] == cpuval and board.board[new_r][new_c] != board.board[0][0]:
            util -= 10
        elif board.board[new_r][new_c] == oppval and board.board[new_r][new_c] != board.board[0][0]:
            util += 10        

    return util

def main():

    human = ''
    while (human != 'B' and human != 'W'):
        print('Please pick your color from B or W:')
        human = input()
    if human == 'B':
        cpu = 'W'
        player = human
        opp = cpu
        print('Player moves first')
    else:
        cpu = 'B'
        player = cpu
        opp = human
        print('CPU moves first')
   
    b = OthelloBoard()
    b.print_board()
    #alternate between human's turn and cpu turn. if there is no available move for one of the players, then
    #it becomes their opponents turn again.
    #if the board is full, the winner is announced
    while(b.is_ended() == False):
        if player == human:
            print("Player: " + player)
            if(b.has_move(player, opp)):
                while True:
                    print("human has move")
                    row, col = -1, -1
                    while (row not in list(range(8))):
                        print("pick a row (0-7)")
                        try:
                            row = int(input())
                        except ValueError:
                            continue
                    while (col not in list(range(8))):
                        print("pick a col (0-7)")
                        try:
                            col = int(input())
                        except ValueError:
                            continue
                            
                    if(b.play_square(col, row, player, opp)):
                        b.print_board()
                        print("__current score__")
                        b.print_score()
                        break
            else:
                print("no move")
            player = cpu
            opp = human
            continue

        elif player == cpu :
            print("Player: " + player)
            if(b.has_move(player, opp)):
                print("cpu has move")
                #make_simple_cpu_move(b,cpu, human)
                make_minimax_cpu_move(b, cpu, human)
                b.print_board()
                print("__current score__")
                b.print_score()
            else:
                print("no move")
            player = human
            opp = cpu
            continue

    sc = b.score(human, cpu)
    print("\n")
    print("::final score::")
    b.print_score()    
    if(sc > 0):
        print("the winner is: " + human)
    elif(sc == 0):
        print("the game is a draw")
    else:
        print("the winner is: " + cpu)

if __name__ == '__main__':
    main()
            
